# 选择排序
def select_sort(data_set):
    l = len(data_set)
    count = 0
    for i in range(0, l - 1):
        min_index = i + 1
        for j in range(i + 1, l):
            if data_set[j] < data_set[min_index]:
                min_index = j
            count += 1

        if data_set[min_index] < data_set[i]:
            data_set[i], data_set[min_index] = data_set[min_index], data_set[i]


# 插入排序+
def insert_sort(data_set):
    l = len(data_set)
    for j in range(1, l):
        while j and data_set[j - 1] > data_set[j]:
            data_set[j - 1], data_set[j] = data_set[j], data_set[j - 1]
            j -= 1
        print(data_set)


# 插入排序2
def insert_sort2(data_set):
    l = len(data_set)
    for i in range(1, l):
        for j in range(i, 0, -1):
            if data_set[j - 1] > data_set[j]:
                data_set[j - 1], data_set[j] = data_set[j], data_set[j - 1]
            else:
                break


# 快速排序
def quick_sort(data_set, min_index, max_index):
    base_index = min_index

    min_i = min_index
    max_i = max_index

    while min_index < max_index:
        # 从右往左边找，直到找到一个数小于基准值
        while max_index > min_index:
            if data_set[max_index] < data_set[base_index]:
                data_set[base_index], data_set[max_index] = data_set[max_index], data_set[base_index]
                base_index = max_index
                break
            else:
                max_index -= 1

        # 从左边往右边找，直到找到一个数大于基准值
        while min_index < max_index:
            if data_set[min_index] > data_set[base_index]:
                data_set[base_index], data_set[min_index] = data_set[min_index], data_set[base_index]
                base_index = min_index
                break
            else:
                min_index += 1

    if min_i < base_index - 1:
        quick_sort(data_set, min_i, base_index - 1)

    if max_i > base_index + 1:
        quick_sort(data_set, base_index + 1, max_i)


def group_by(data_set, n):
    for i in range(0, n):
        data_units = list()
        for j in range(i, len(data_set), n):
            data_units.append(j)
        yield data_units


def insert_sort_by_index(data_set, index_set):
    l = len(index_set)
    for j in range(1, l):
        while j and data_set[index_set[j - 1]] > data_set[index_set[j]]:
            data_set[index_set[j - 1]], data_set[index_set[j]] = data_set[index_set[j]], data_set[index_set[j - 1]]
            j -= 1


# SHELL排序
def shell_sort(dataset):
    l = len(dataset)
    gap = l // 2

    while gap > 0:
        for group in group_by(dataset, gap):
            insert_sort_by_index(dataset, group)
        gap = gap // 2


# 归并排序
def merg_set(l1, l2):
    l1_idx = 0
    l2_idx = 0

    new_list = []
    while l1_idx < len(l1) and l2_idx < len(l2):
        if l1[l1_idx] < l2[l2_idx]:
            new_list.append(l1[l1_idx])
            l1_idx += 1
        else:
            new_list.append(l2[l2_idx])
            l2_idx += 1

    while l1_idx < len(l1):
        new_list.append(l1[l1_idx])
        l1_idx += 1

    while l2_idx < len(l2):
        new_list.append(l2[l2_idx])
        l2_idx += 1

    return new_list


def merg_sort(dataset):
    l = len(dataset)
    if l <= 2:
        if l == 2:
            if dataset[0] > dataset[1]:
                dataset[0], dataset[1] = dataset[1], dataset[0]
        return dataset

    index = l // 2
    part1 = dataset[0:index]
    part2 = dataset[index:]

    part1 = merg_sort(part1)
    part2 = merg_sort(part2)

    return merg_set(part1, part2)


# l1 = [1, 5, 9]
# l2 = [2, 4]

# print(merg_set(l1, l2))

data_set = [29, 45, 12, 3, 87, 94, 63, 19, 78]
print(merg_sort(data_set))
# print(data_set)
# index_set = [8, 6, 3]
#
# for i in index_set:
#     print(data_set[i])
# insert_sort_by_index(data_set, index_set)
# for i in index_set:
#     print(data_set[i])
# print(index_set)
# quick_sort(data_set, 0, len(data_set) - 1)
# print(data_set)
# group_by(data_set, 3)
